Optimal account balancing

Time: O(Nx2^N); Space: O(2^N); hard

Given a directed graph where each edge is represented by a tuple, such as [u, v, w]represents an edge with a weight w from u to v.

You need to calculate at least the need to add the number of edges to ensure that each point of the weight are balancing. That is, the sum of weight of the edge pointing to this point is equal to the sum of weight of the edge of the point that points to the other point.

Notes:

  • u != v and w > 0.

  • Index may not be linear, e.g. we could have the points 0, 1, 2 or we could also have the points 0, 2, 6.

Example 1:

Input: transactions = [[0,1,10],[2,0,5]]

Output: 2

Explanation:

  • Two edges are need to added. There are [1,0,5] and [1,2,5]

Example 2:

Input: transactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]

Output: 1

Explanation:

  • Only one edge need to added. There is [1,0,4]

[1]:

import collections

class Solution1(object):
    """
    Time: O(N*2^N), N is the size of the debt.
    Space: O(2^N)
    """
    def minTransfers(self, transactions):
        """
        :type transactions: List[List[int]]
        :rtype: int
        """
        accounts = collections.defaultdict(int)

        for transaction in transactions:
            accounts[transaction[0]] += transaction[2]
            accounts[transaction[1]] -= transaction[2]

        debts = [account for account in accounts.values() if account]

        dp = [0]*(2**len(debts))
        sums = [0]*(2**len(debts))

        for i in range(len(dp)):
            for j in range(len(debts)):
                if (i & (1<<j)) == 0:
                    nxt = i | (1<<j)
                    sums[nxt] = sums[i]+debts[j]

                    if sums[nxt] == 0:
                        dp[nxt] = max(dp[nxt], dp[i]+1)
                    else:
                        dp[nxt] = max(dp[nxt], dp[i])

        return len(debts)-dp[-1]

[2]:

s = Solution1()

transactions = [[0,1,10],[2,0,5]]
assert s.minTransfers(transactions) == 2

transactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]
assert s.minTransfers(transactions) == 1